package seqlist.queue.impl;

import seqlist.queue.Queue;

import java.util.NoSuchElementException;

/**
 * 基于链表实现的普通队列
 */

class Node<E>{
    E val;//保存元素的值
    Node<E> next;//保存下一个的地址

    public Node(E val) {
        this.val = val;
    }
}

public class LinkedQueue<E> implements Queue<E> {
    //当前队列中的元素个数
    private int size;
    //当前队列的对首元素
    private Node<E> head;
    //当前队列的尾部元素
    private Node<E> tail;

    @Override
    public void offer(E val) {
        //产生一个新节点
        Node<E> node = new Node<>(val);
        if(head == null){
            head = node;
        }else{
            tail.next = node;
        }
        tail = node;//因为队列实行的是尾插，这步不管是否为空都执行
        size ++;
    }

    @Override//出队操作
    public E poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        //删除当前的对首元素，即head
        E val = head.val;
        Node<E> node = head;//保存待删除的头节点
        head = head.next;//换头节点位置
        node.next = null;//断开连接
        size --;
        return val;
    }

    @Override //查看队首元素
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        return head.val;
    }

    @Override //判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //模拟实现toString方法
    @Override
    public String toString() {
       StringBuilder sb = new StringBuilder();
       sb.append("front [");

        for (Node<E> x = head; x != null; x = x.next) {
            sb.append(x.val);
            if(x.next != null)
                sb.append(" -> ");
        }
        sb.append("] tail");
        return sb.toString();
    }

}
